#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    bool dp[1000][1000] = { 0 };
    void _solve(vector<vector<int>>& arr, int& lenmax, int len, int x, int y) {
        int n = arr.size(), m = arr[0].size();
        for (int k = 0; k < 4; k++) {
            int a = x + dx[k], b = y + dy[k];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (dp[a][b] == true) continue;
            if (arr[a][b] > arr[x][y]) {
                dp[a][b] = true;
                lenmax = max(lenmax, len);
                _solve(arr, lenmax, len + 1, a, b);
            }
            dp[a][b] = false;
        }
    }
    int solve(vector<vector<int> >& matrix) {
        int ret = 0, lenmax = 1;
        for (int i = 0; i < matrix.size(); i++)
            for (int j = 0; j < matrix[0].size(); j++)
            {
                int len = 2;
                _solve(matrix, lenmax, len, i, j);
                ret = max(ret, lenmax);
            }
        return ret;
    }
};

#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int memo[1000][1000] = { 0 };
    int _solve(vector<vector<int>>& arr, int x, int y) {
        if (memo[x][y]) return memo[x][y];
        int n = arr.size(), m = arr[0].size();
        int len = 1;
        for (int k = 0; k < 4; k++) {
            int a = x + dx[k], b = y + dy[k];
            if (a >= 0 && a < n && b >= 0 && b < m && arr[a][b] > arr[x][y])
                len = max(len, 1 + _solve(arr, a, b));
        }
        memo[x][y] = len;
        return len;
    }
    int solve(vector<vector<int> >& matrix) {
        int ret = 0;
        for (int i = 0; i < matrix.size(); i++)
            for (int j = 0; j < matrix[0].size(); j++)
                ret = max(ret, _solve(matrix, i, j));
        return ret;
    }
};